import java.util.*;

public class SingleCircularList {
    // 定义链表节点类
    static class Node {
        int data; // 节点存储的数据
        Node next; // 指向下一个节点的引用
        // 节点构造函数，初始化数据
        Node(int data) {
            this.data = data;
            this.next = null; // 新节点初始化时，next为null，后续构建循环时调整
        }
    }
    Node head; // 头节点（哨兵节点，方便操作，不存储实际有效数据）
    int length; // 链表长度

    // 链表构造函数，初始化链表
    public SingleCircularList() {
        head = new Node(-1); // 头节点数据设为-1，仅作标记
        head.next = head; // 头节点指向自己，形成空循环链表
        length = 0; // 初始长度为0
    }

    // 头插法：在链表头部插入新节点
    public void addAtHead(int data) {
        Node newNode = new Node(data); // 创建新节点
        newNode.next = head.next; // 新节点的next指向原头节点后的第一个节点
        head.next = newNode; // 头节点的next指向新节点，完成头插
        length++; // 链表长度加1
    }

    // 尾插法：在链表尾部插入新节点
    public void addAtTail(int data) {
        Node newNode = new Node(data); // 创建新节点
        Node last = head; // 从头部开始找尾节点
        // 循环直到找到尾节点（尾节点的next指向head）
        while (last.next != head) {
            last = last.next;
        }
        last.next = newNode; // 尾节点的next指向新节点
        newNode.next = head; // 新节点的next指向头节点，形成循环
        length++; // 长度加1
    }

    // 删除指定数据的节点
    public boolean deleteNode(int data) {
        Node cur = head.next; // 从第一个有效节点开始遍历
        Node prev = head; // 记录当前节点的前驱节点
        while (cur != head) { // 未遍历完整个链表
            if (cur.data == data) { // 找到目标节点
                prev.next = cur.next; // 前驱节点跳过当前节点，实现删除
                length--; // 长度减1
                return true; // 删除成功
            }
            prev = cur; // 前驱节点后移
            cur = cur.next; // 当前节点后移
        }
        return false; // 遍历完未找到，删除失败
    }

    // 反转链表
    public void reverse() {
        // 若链表为空或只有一个节点，无需反转
        if (head.next == head || head.next.next == head) return;
        Node prev = head; // 前驱指针，初始指向头节点
        Node cur = head.next; // 当前指针，初始指向第一个有效节点
        Node next; // 临时存储当前节点的下一个节点
        while (cur != head) { // 遍历链表
            next = cur.next; // 保存当前节点的下一个节点
            cur.next = prev; // 当前节点的next指向前驱，实现反转
            prev = cur; // 前驱后移到当前节点
            cur = next; // 当前节点后移到原下一个节点
        }
        // 调整头节点的next，完成反转后的循环
        head.next.next = head;
        head.next = prev; // 头节点指向新的头部（原尾节点）
    }

    // 打印链表信息
    public void printList() {
        Node cur = head.next; // 从第一个有效节点开始
        System.out.print("当前链表: ");
        while (cur != head) { // 遍历打印每个节点的数据
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
        System.out.println("length: " + length); // 打印链表长度
    }
}

class Main {
    public static void main(String[] args) {
        SingleCircularList linkedList = new SingleCircularList();
        System.out.println("------------初始化链表------------");
        System.out.println("head= 00000000091250 ");

        // 头插法添加结点
        System.out.println("------------增加结点(头插法)------------");
        linkedList.addAtHead(13);
        linkedList.addAtHead(14);
        linkedList.addAtHead(15);
        linkedList.printList();

        // 尾插法添加结点
        System.out.println("------------增加结点(尾插法)------------");
        linkedList.addAtTail(21);
        linkedList.addAtTail(22);
        linkedList.addAtTail(23);
        linkedList.printList();

        // 删除结点
        System.out.println("------------删除结点------------");
        System.out.println("删除数据为5120的结点");
        System.out.println("删除前:");
        linkedList.printList();
        linkedList.deleteNode(5120);
        linkedList.printList();

        System.out.println("删除数据为13的结点");
        System.out.println("删除前:");
        linkedList.printList();
        linkedList.deleteNode(13);
        linkedList.printList();

        System.out.println("删除数据为23的结点");
        System.out.println("删除前:");
        linkedList.printList();
        linkedList.deleteNode(23);
        linkedList.printList();

        // 反转链表
        System.out.println("------------反转链表------------");
        System.out.println("-----反转前");
        linkedList.printList();
        linkedList.reverse();
        System.out.println("-----反转后");
        linkedList.printList();
    }
}